package heap

// parent (k - 1) / 2
// left   2*k + 1
// right  2*k +2

type maxHeap []int

func (h *maxHeap) Len() int {
	return len(*h)
}

func (h *maxHeap) Swap(i,j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *maxHeap) Less(i, j int) bool {
	return (*h)[i] < (*h)[j]
}

func (h *maxHeap) Push(v interface{}) {
	*h = append(*h, v.(int))
	h.up(h.Len() - 1)
}

func (h *maxHeap) Pop() (v interface {}) {
	n := h.Len() - 1
	h.Swap(0, n)
	h.down(0, n)
	*h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
	return
}

func (h *maxHeap) down(k, n int) {
	i := k
	//e := (*h)[i]
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
			break
		}
		j := j1 // left child
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // = 2*i + 2  // right child
		}
		if !h.Less(j, i) {
			break
		}
		//if e < (*h)[j] { break }
		h.Swap(i, j)
		//(*h)[i] = (*h)[j]
		i = j
	}
	//(*h)[i] = e
}

func (h *maxHeap) up(j int) {
	for {
		i := (j - 1) / 2 // parent
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

func HeapSort(arr []int) {
	h := new(maxHeap)
	n := len(arr)
	for i := 0; i < n; i++ {
		h.Push(arr[i])
	}
	for i := 0; i < n; i++ {
		arr[i] = h.Pop().(int)
	}
}

func HeapSort2(arr []int) {
	n := len(arr)
	a1 := make([]int, n)
	copy(a1, arr)
	h := maxHeap(a1)
	// heapify
	for i := (n - 1)/2; i >= 0; i-- {
		h.down(i, n)
	}
	for i := 0; i < n; i++ {
		arr[i] = h.Pop().(int)
	}
}

func HeapSort3(arr []int) {
	n := len(arr)
	h := maxHeap(arr)
	// heapfipy
	for i := (n - 1)/2; i >= 0; i-- {
		h.down(i, n)
	}

	for i := n - 1; i >=0; i-- {
		h[0], h[i] = h[i], h[0]
		h.down(0, i)
	}
	for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
		arr[i], arr[j] = arr[j], arr[i]
	}
}